# @Time    : 2020/11/18 12:04 下午
# @Author  : baii
# @File    : 56. 合并区间
# @Use     :
"""
题目: https://leetcode-cn.com/problems/merge-intervals/
"""
from typing import List


class Solution:
    """
    时间复杂度：O(nlog2n) + O(n)
    空间复杂度：小于 O(n)
    """
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:

        def take(e: List[int]) -> int:
            return e[0]

        # 排序 O(nlog2n)
        intervals.sort(key=take)

        ret = [intervals[0]]

        for e in intervals[1:]:
            if ret[-1][1] > e[0]:
                # 如果左边区间的最大值 大于右边区间的最小值 那就合并两个区间
                ret[-1][1] = e[1]
            else:
                # 否则这个区间不能合并
                ret.append(e)

        return ret



if __name__ == '__main__':
    intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
    print(Solution().merge(intervals))